1. Field of the Invention
The present invention relates to a method of controlling the access to a recording disk requiring a high transfer speed and access to discontinuous positions on the disk (random access) and to an apparatus for the same.
2. Description of the Related Art
Along with the increase of the speed of computers, disk storage devices which enable high speed, random access have been becoming increasingly important. In recent years, particularly in technology for multimedia, now the focus of so much attention, it is essential to access the motion pictures and audio stored on the disk as digital data at a high speed and from positions on the disk separate from each other. Namely, a high transfer speed and real time property are required for the storage of multimedia data such as motion pictures and audio. The high transfer speed naturally becomes necessary when handling a large amount of motion pictures and audio.
Furthermore, the real time property requires that an upper limit of the processing time not be exceeded. For example, the movement becomes awkward unless 30 frames are successively displayed per second at constant intervals in the motion picture.
Further, if not able to keep up with the capabilities of the disk and there is insufficient audio data, the sound breaks off and unpleasant noise is generated. In this way, if the data of multimedia are not prepared and used at their respectively specified times, the value of the information drops sharply. Accordingly, in the storage for multimedia, it is important that the upper limit be guaranteed, that is, that the processing can be carried out in that time even in the worst case. Otherwise, even if satisfying the specifications in terms of the average performance, it is possible that the data will be too late at some periods of time. The guarantee of the maximum value of the processing time is referred to as the real time property and is an indispensable function in the multimedia field.
In the storage of information for computers, improvement of average performance has been the primary target. The worst value was not always kept low; that is, there was a large variation in storage processing time. This point stands in sharp contrast to storage requirements for multimedia.
In addition, in the main fields of application of multimedia, successive access to data at physically separated positions (random access) must be able to be carried out at a high speed. For example, video-on-demand (VOD) is a system allowing a large number of viewers to call up and view the programs they like at the times they like. In order to realize this, it is necessary to process the requests from many viewers in parallel and quickly prepare the data of the parts that the viewers are currently watching. For this reason, it becomes necessary to trace the sources of movies, etc. stored at a variety of locations on the disk at a high speed.
Further, in recent years, videos and movies have been edited by using not tapes and films, but disks. With a tape, when inserting a scene of a few seconds into a position near the start of a program of, for example, one hour, to prevent overwriting it is necessary to shift to the rear all of the video after that insertion position and therefore re-record the program. Unlike high speed reproduction of analog audio cassette tapes, such re-recording of video programs requires about one program's worth of time, so the efficiency is poor. With a disk, however, since random access is possible, it is possible to place the insertion portion at another position on the disk, jump once to that position and access the inserted video at the time of reproduction, and then return to the original position and continue the reproduction of the video. Taking this methodology a step further, there is known a technique wherein each scene (cut) of the program is placed at different positions on the disk and track them at a high speed at the time of reproduction so as to make it appear as if a single tape were being reproduced. By doing this, it is possible to switch scenes and change lengths just by changing the order of tracking of the data on the disk, therefore the efficiency of editing is extremely high. This is referred to as non-linear editing. Note that, in this case as well, it is necessary to track physically separated positions on the disk at a high speed.
As seen in these examples, in the fields of application of multimedia, it is extremely important to access the data at a high speed while tracking discontinuous positions on the disk (this is referred to as random access), but the time for the movement of the head to the desired cylinder, which is referred to as the seek time, and the time for waiting for the disk to rotate until the start of the data appears in the cylinder, which is referred to as the rotational delay time, are necessary for movement to discontinuous positions. These times are referred to as the overhead of the access. The longer this is compared with the time for actually accessing the data, the longer time it takes for the transfer of data from the disk and therefore the lower the performance.
Now, when assuming that the seek time of the disk is Ts and the rotational delay time is Tr, the overhead of the disk access becomes Ts+Tr. When the head of the disk exists in the data and the time for actually accessing the data is Tt, the efficiency compared with a case where there is no jump of the head to a separate position becomes low as shown in the following Equation (1): EQU Tt/(Tt+Ts+Tr) (1)
Namely, in comparison with a case where the data on the disk are sequentially accessed from start to the end, in the case where random access is carried out while tracking the data at separated positions, it is necessary to be aware of the reduction of the performances by that amount. Accordingly, the task with multimedia disks is to suppress the reduction in the performance at the time of a random access while maintaining the real time property (to determine the upper limit of the processing time and guarantee to always operate at a time equal to or shorter than this upper limit).
In recent years, research has been conducted regarding the method of guaranteeing the real time property in the access of disks. For example, in D. Anderson, Y. Osawa, and R. Govindan, "A File System for Continuous Media", ACM Transactions on Computer Systems, Vol. 10, No. 4, pp. 311-337, 1992 (hereinafter referred to as "Anderson 92"), an attempt is made to improve the performance of a system by optimizing the relationship between the amount of the buffer memory for temporarily storing the data read from the disk and the amount of the data to be read in a single access.
When it comes to the overhead of the access of the disk, however, to facilitate the analysis, it assumes that the worst values conceivable both for the seek time and the rotational delay time occur at every random access. Namely, the time when seeking from the innermost circumference to the outermost circumference is adopted as the seek time and the time for waiting for exactly one rotation is adopted as the rotational delay time. Of course, if making this assumption, the estimate of the worst value of the processing time is extremely safe, but such an operation is not conducted every time in actuality and therefore the estimate of the worst value becomes very low in comparison with the performance which can be derived from the disk in actuality and such an estimate has little significance as design data.
Further, in V. Rangan and H. Vin, "Efficient Storage Technique for Digital Continuous Multimedia", IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 4, pp. 564-573, 1993 (hereinafter referred to as "Rangan 93"), it is investigated how, when cutting a video file into a plurality of segments and storing the different segments at different positions, to determine the lengths of the segments and the intervals between segments so as to maintain the real time property.
Here too, however, when jumping between segments (at time of random access), it is assumed that the worst overhead is caused every time in the same way as described in "Anderson 92", therefore a similar problem exists.
There have also been attempts to keep the worst value lower in comparison with these studies. These enable real time random access to be guaranteed with much higher performances. Each of N. Reddy and J. Wyllie, "Disk Scheduling in a Multimedia I/O System", ACM multimedia 93, pp. 225-233, 1993 (hereinafter referred to as "Reddy 93"), J. Gemmel, J. Han, et al., "Delay-Sensitive Multimedia on Disk", IEEE Multimedia 1994, pp. 56-67, 1994 (hereinafter referred to as "Gemmel 94"), and M. Chen, D. Kandlur, and P. Yu, "Optimization of the Grouped Sweeping Scheduling (GSS) with Heterogeneous Multimedia Streams", ACM Multimedia 93, pp. 235-242, 1993 (hereinafter referred to as "Chen 93"), attempts to suppress the overhead by using a head scheduling algorithm referred to as "SCAN".
"Head scheduling" is a method for reducing the seek time by tinkering with the order of the access where it is necessary to access a plurality of positions on the disk. The SCAN algorithm shown in FIG. 1 is an algorithm in which a given plurality of I/O requests (#1, #2, . . . ) are sorted in the radial direction of the disk and sequentially processed. Reciprocal operation of the head, which will occur if the processing is carried out in the order of arrival of the I/O requests (#1, #2, . . . ), can be prevented and in turn the respective seek times can be reduced. As the algorithm of the head scheduling, many algorithms are known. These are mentioned in detail in for example H. Deitel, "Operating Systems", Addison Wesley, pp. 360-372, 1990.
All of "Reddy 93", "Gemmel 94", and "Chen 93" are predicated on the assumption the use of a SCAN algorithm, therefore are able to suppress the seek time. Accordingly, it is possible to lower the worst value of the overhead and guarantee a higher performance in comparison with "Anderson 92" and "Rangan 93".
However, the only thing which the SCAN algorithm can suppress is the seek time. No allusion has yet been made up to now about reduction of the rotational delay time.
"Reddy 93" assumes that a special function referred to as a zero latency access mechanism exists in the disk. The zero latency access mechanism is a method in which the data is successively read even from the middle of the data at a point of time when the head reaches the desired track and the leading portion of the data which was not in time is read again when the disk rotates one time and that portion returns. Accordingly, when the disk rotates one time, the desired data can be all reliably read and therefore the total of the rotational delay and the access of data becomes the time of the amount of one rotation at the maximum.
However, since few actual disks utilize this mechanism, it may be that the assumption in "Reddy 93" is not realistic.
On the other hand, "Gemmel 94" adopts a method of estimating the overhead by always adding the maximum value as a result of considering that the rotational delay is an amount for which control and prediction are impossible. This is safe but there is a lot of waste, which poses a problem. Further, "Chen 93" treats the rotational delay as a negligible correction term, but this is not realistic. For example, in recent high speed disks, the rotation cycle is 8.3 mS, while if the SCAN algorithm is used, the maximum value of the seek time can be suppressed to about 6 ms or less. Therefore the rotational delay is dominant. Further, from the viewpoints of the air resistance and the consumed electric power of the motor and resultant heat generated, it is difficult to expect any epoch-making improvements in the rotational speed from this point onward. The reduction of the rotational delay is the biggest problem which should be solved.
It is also pointed out that in the usual file system for computers, the reduction of the rotational delay is important. S. Ng, "Improving Disk Performance Via Latency Reduction", IEEE Transactions on Computers, Vol. 40, No. 1, January 1991, pp. 22-30, 1991 (hereinafter referred to as "Ng 91") mentions a method of reducing the average rotational delay time at the time of a read operation by the method of preparing a copy of the data shifted in phase in the rotational direction etc. However, it is difficult to apply this method for multimedia applications which involve a huge amount of data.